package com.mlh.dp.old;
//
// 题目：
// 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
// 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
// 举例：
// 输入：arr = [1,2,3,4], difference = 1
// 输出：4
// 解释：最长的等差子序列是 [1,2,3,4]。

import java.util.HashMap;
import java.util.Map;

public class LongestSubsequence {
    //和前面相同的做法
    //但是提交执行时间过长
    //算法需要优化
    public static int method1(int[]arr,int difference){
        int[]dp=new int[arr.length];
        int max=0;
        for(int i=0;i<dp.length;i++){
            dp[i]=1;
            for(int j=i-1;j>=0;j--){
                if(arr[i]-difference==arr[j]){
                    if(dp[i]<dp[j]+1){
                        dp[i]+=dp[j];
                    }
                }
            }
            max=max>dp[i]?max:dp[i];
        }
        return max;
    }

    //这里利用hashmap来进行优化  因为这里是temp-difference=前面某个数  可以利用hashmap结构来实现快速查找
    //用hashmap代替dp数组 降低时间复杂度
    public static int method2(int[] arr, int difference) {
        Map<Integer,Integer>box=new HashMap<>();
        int max=0;
        for(int temp:arr){
            // key映射不存在与HashMap中
            // NotFound 若HashMap中没有这个key 则返回默认数值
            box.put(temp,box.getOrDefault(temp-difference,0)+1);
            max=Math.max(max,box.get(temp));
        }
        return max;
    }
}
